📋 Problem
In TitanCode Arena, N players have combat power scores in an array (index 0 is top-ranked). Support two operations:
- Query:
Q L R— print maximum value in range [L,R]. - Update:
U i val— set arr[i] = val.
Use a Segment Tree for efficient updates and queries.
✅ Constraints (provided)
1 ≤ N, Q ≤ 20. Values ≤ 20. 0-based indices.
📌 Examples
Input:
6 5
4 7 2 9 5 1
Q 1 4
U 3 6
Q 1 4
U 0 10
Q 0 2
Output:
9
7
10
🧠 Algorithm & C++ Code
Build tree: O(N). Query & Update: O(log N) per op.
// Segment Tree (Range Max) - GCC compatible (single-file)
#include <bits/stdc++.h>
using namespace std;
vector<int> tree;
int n;
void build(vector<int>& a,int node,int l,int r){
if(l==r) tree[node]=a[l];
else{int mid=(l+r)/2; build(a,2*node,l,mid); build(a,2*node+1,mid+1,r);
tree[node]=max(tree[2*node],tree[2*node+1]);
}
}
int query(int node,int l,int r,int ql,int qr){
if(qr<l || r<ql) return INT_MIN;
if(ql<=l && r<=qr) return tree[node];
int mid=(l+r)/2;
return max(query(2*node,l,mid,ql,qr), query(2*node+1,mid+1,r,ql,qr));
}
void update(int node,int l,int r,int idx,int val){
if(l==r){ tree[node]=val; return; }
int mid=(l+r)/2;
if(idx<=mid) update(2*node,l,mid,idx,val); else update(2*node+1,mid+1,r,idx,val);
tree[node]=max(tree[2*node],tree[2*node+1]);
}
int main(){
ios::sync_with_stdio(false);cin.tie(NULL);
int N,Q; if(!(cin>>N>>Q)) return 0;
vector a(N); for(int i=0;i>a[i];
tree.assign(4*N,INT_MIN);
build(a,1,0,N-1);
while(Q--){
char t; cin>>t;
if(t=='Q'){int L,R;cin>>L>>R; cout<>idx>>val; update(1,0,N-1,idx,val);}
}
}
Array preview
Query outputs
-
Operation log
Build the tree to begin.
Segment Tree (full)
Controls